💾 Organização de Arquivos de Dados

Objetivo: dada uma sequência de INSERT, DELETE e UPDATE, desenhar como fica o arquivo de dados de cada tabela: em que bloco e em que slot cada tupla mora (o rid), o que vai para a free list e quando uma tupla migra.

🧭 Comece aqui

A ideia em uma frase. O disco não lê um dado de cada vez: ele lê páginas inteiras, como um caderno em que você só consegue abrir uma página por vez. O banco guarda cada tabela num arquivo feito dessas páginas, chamadas blocos, todas do mesmo tamanho (ex.: 256 bytes). Cada linha da tabela ocupa um pedaço de algum bloco. Este cheat sheet ensina a responder: depois desses comandos, em que bloco e em que posição ficou cada linha?

O que a questão pede. Um desenho dos blocos do arquivo, com cada linha no lugar certo ([chave, ...]), os espaços vazios, a lista de espaços livres e o cabeçalho do arquivo.

Palavras que vão aparecer:

• Tupla (ou registro): uma linha da tabela.
• Bloco (ou página): um pedaço de tamanho fixo do arquivo. É a unidade que o disco lê.
• Slot: a posição de uma tupla dentro do bloco (1ª, 2ª, 3ª…).
• rid (row id): o endereço da tupla, formado pelo número do bloco + número do slot. 0302 é o bloco 03, slot 02.
• Free list: a lista dos buracos que os DELETE deixaram, no formato <rid, tamanho>, para reaproveitar depois.
• PCTFREE: a porcentagem de cada bloco que o INSERT deixa vazia, para as tuplas crescerem num UPDATE futuro.
• Migração: quando um UPDATE aumenta a tupla e ela não cabe mais no bloco. Ela muda de lugar e de rid.

arquivo da tabela product (blocos de 256 B)

bloco 01:  [W10]  [AZA]  [NB2]  [WRF]  [MSP]     ← 5 tuplas, sobram 2 B
            0101   0102   0103   0104   0105     ← rid = bloco + slot
bloco 02:  [WRP]  [AMP]  [WFL]  [RSR]  [GN2]
            0201   0202   0203   0204   0205

Onde este arquivo se encaixa. É o 1º de 3. Os rids que saem daqui são exatamente o que o índice guarda nas folhas ("Banco de Dados: Indexação e Árvore B+"). O número de blocos de cada tabela é a base de toda conta de custo ("Banco de Dados: Custo de Consultas").

Se você está perdido, leia nesta ordem: este "Comece aqui", depois o Exemplo resolvido (seção 8) acompanhando a Receita (seção 7) passo a passo. As seções 1 a 6 são de consulta: volte a elas quando uma conta do exemplo não fizer sentido.

🧱 1. Conceitos de apoio

Estrutura do bloco (slotted page). O bloco começa com um header que guarda o número de entradas e um diretório de slots (posição e tamanho de cada registro). Os registros crescem do fim para o começo, e o espaço livre fica no meio. O rid aponta para o slot, então mover um registro dentro do próprio bloco não muda o rid.

┌─────────────┬────────┬────────┬────────┬─────────────┬────┬────┬────┐
│ nº entradas │ slot 1 │ slot 2 │ slot 3 │  → livre ←  │ R3 │ R2 │ R1 │
└─────────────┴────────┴────────┴────────┴─────────────┴────┴────┴────┘
 └──── header do bloco (diretório de slots) ───┘        registros ←──

⚠️ Se o enunciado não der o tamanho do header do bloco, não desconte nada: o bloco inteiro é espaço útil.

Organizações de arquivo

Remoção: ou se reescreve o bloco (compactando), ou se usa marcador de remoção + free list. No segundo caso, o buraco fica onde está e é reaproveitado depois. É o modelo do exercício.

📏 2. Tamanho de cada registro

O tamanho do registro é a soma dos campos: $R = \sum \text{campos}$.

• 🔢 Um valor '1' (texto) numa coluna INT é convertido e continua ocupando o tamanho do INT.
• 🔢 DEFAULT nextval('seq') numera na ordem dos INSERT: 1, 2, 3, …
• 📐 Prefixo de tamanho do VARCHAR e header de bloco só entram na conta quando o enunciado os informa.

🧮 3. PCTFREE: reserva para UPDATE

$$\text{limite do INSERT} = \left\lfloor B \times \left(1 - \frac{\text{PCTFREE}}{100}\right) \right\rfloor$$

• PCTFREE 5 com bloco de 256 B: $\lfloor 256 \times 0{,}95 \rfloor = \lfloor 243{,}2 \rfloor = 243$ B para INSERT. Os 13 B restantes (5% de 256) ficam reservados.
• PCTFREE 0: o INSERT pode usar os 256 B.
• O INSERT ocupa só até o limite. O UPDATE pode usar a reserva, até encher o bloco ($B$).

🔀 4. Em que bloco o INSERT cai

• Nenhum bloco serve → abre um bloco novo no fim do arquivo, e o header ganha +1 bloco.
• ⚠️ No first-fit, uma tupla inserida depois pode cair num bloco anterior, se ainda houver espaço lá. É aqui que a resposta muda de uma política para outra.
• ⚠️ Tupla maior que o buraco, mas que caberia somando o buraco ao resto do espaço livre do bloco: isso depende de compactar o bloco. Diga o que assumiu.

🗑️ 5. Efeito de cada operação

• 🔗 A chave estrangeira de outras tabelas não muda: ela guarda o valor (ex.: brand_id = 1), não o endereço.
• 📌 No modelo deste exercício, o rid muda e os índices são corrigidos. SGBDs como o Oracle mantêm o rid deixando um ponteiro de encaminhamento no slot antigo (row migration). Use essa variante só se o enunciado pedir.

🖼️ 6. Como desenhar a resposta

• rid no formato PPRR: PP é o bloco e RR o slot dentro do bloco, ambos a partir de 01. 0302 é o 2º registro do 3º bloco.
• Cada tupla é [chave, ...], e cada buraco é (livre, N B). Anote a ocupação de cada bloco, o header e a free list.

<tabela>   header: N blocos   free list: <PPRR, tamanho> -> ...
┌─ bloco 01 ──────────────────────────────────────────────┐
│ [chave, ...] [chave, ...] (livre, 46 B) [chave, ...]    │ usado/B
├─ bloco 02 ──────────────────────────────────────────────┤
│ [chave, ...] [chave, ...]                               │ usado/B
└─────────────────────────────────────────────────────────┘

✅ 7. Receita na prova

1. Tamanho de cada tupla: some os campos (CHAR cheio, VARCHAR pelo uso, × bytes por caractere). Faça uma tabela com uma linha por tupla, incluindo o tamanho depois de cada UPDATE.
2. Limite do INSERT de cada tabela, pelo PCTFREE (arredonde para baixo).
3. Insira uma por uma pela política do enunciado, anotando a ocupação de cada bloco e o rid.
4. DELETE: apague sem mover ninguém e anote <rid, tamanho> na free list, em ordem de rid.
5. INSERT depois de DELETE: confira os buracos da free list antes do fim dos blocos (o first-fit percorre na ordem).
6. UPDATE: veja se cabe no bloco usando a reserva. Se não cabe, migre, mude o rid e diga que os índices são corrigidos.
7. Desenhe o arquivo final: header, free list e blocos com ocupação. Escreva a política que aplicou.

📝 8. Exemplo resolvido completo

Enunciado (resumido). Bloco de 256 B, INT de 8 B, charset de 2 bytes por caractere, registros não extrapolam blocos, armazenamento orientado a linha. Política de (re)uso de blocos: first-fit. Free list com <rid, tamanho> ordenada por rid. O header do arquivo guarda o número de blocos.

CREATE TABLE brand (id INT DEFAULT nextval('brand_id_seq'), name CHAR(10),
                    description VARCHAR(100), ...) PCTFREE 5;
CREATE TABLE product (id CHAR(3), name VARCHAR(50), brand_id INT,
                      sold_units INT, ...) PCTFREE 0;
INSERT INTO brand ...  'Nike' (50 chars), 'Asics' (80), 'Mizuno' (40)
INSERT INTO product ... W10, AZA, NB2, WRF, MSP, WRP, RV6, WFL, RSR, GN2,
                        RV7, GE2, CR3              -- nesta ordem
DELETE FROM product WHERE id IN ('RV6', 'RV7');
INSERT INTO product ... ('AMP', 'Air Max Plus', '1', 1200);
UPDATE brand SET description = <75 chars> WHERE name = 'Nike';

Passo 1. Tamanhos.

• product: CHAR(3) 6 + INT 8 + INT 8 = 22 fixos, mais o nome × 2.
• brand: INT 8 + CHAR(10) 20 = 28 fixos, mais a descrição × 2.

Passo 2. Limites. brand: $\lfloor 256 \times 0{,}95 \rfloor = 243$ B por INSERT. product: 256 B.

Passo 3. product por first-fit.

W10 40 → bloco 01 ( 40)      WRP 56 → 01 tem 2 livres → abre 02 ( 56)
AZA 54 → bloco 01 ( 94)      RV6 46 → 02 (102)
NB2 40 → bloco 01 (134)      WFL 44 → 02 (146)
WRF 60 → bloco 01 (194)      RSR 52 → 02 (198)
MSP 60 → bloco 01 (254)      GN2 42 → 02 (240)
RV7 46 → 01 tem 2, 02 tem 16: nenhum serve → abre 03 (46)
GE2 42 → 03 (88)             CR3 40 → 03 (128)

Passo 4. brand: aqui o first-fit muda a resposta.

Nike   128 → bloco 01                                   (128 de 243)
Asics  188 → 01 tem 243 − 128 = 115 livres, não cabe → abre 02 (188)
Mizuno 108 → 01 tem 115 livres, 108 ≤ 115: CABE → bloco 01, rid 0102

Passo 5. DELETE e o INSERT do AMP.

DELETE RV6, RV7  → free list: <0202, 46> → <0301, 46>
INSERT AMP (46)  → 1º da lista: <0202, 46>, 46 ≤ 46, serve → AMP em 0202
free list final  → <0301, 46>

Passo 6. UPDATE da Nike: não cabe e migra. A Nike cresce de 128 para 178 B (+50). O bloco 01 ficaria com 178 + 108 (Mizuno) = 286 > 256: não cabe nem usando a reserva. Ela sai do slot 0101, que vira <0101, 128> na free list, e é reinserida por first-fit. O buraco 0101 tem 128 < 178. O bloco 01 ficaria com 108 + 178 = 286, e o bloco 02 com 188 + 178 = 366. Nenhum serve, então ela abre o bloco 03, rid 0301. Os índices pk_brand e uk_brand_name são corrigidos, e o brand_id de product continua 1.

Resposta.

product   header: 3 blocos   free list: <0301, 46>
┌─ bloco 01 ──────────────────────────────────────────────┐
│ [W10, ...] [AZA, ...] [NB2, ...] [WRF, ...] [MSP, ...]  │ 254/256
├─ bloco 02 ──────────────────────────────────────────────┤
│ [WRP, ...] [AMP, ...] [WFL, ...] [RSR, ...] [GN2, ...]  │ 240/256
├─ bloco 03 ──────────────────────────────────────────────┤
│ (livre, 46 B) [GE2, ...] [CR3, ...]                     │  82/256
└─────────────────────────────────────────────────────────┘

brand   header: 3 blocos   free list: <0101, 128>
┌─ bloco 01 ─────────────────┐
│ (livre, 128 B) [3, ...]    │ 108/256  ← slot 0101 era da Nike
├─ bloco 02 ─────────────────┤
│ [2, ...]                   │ 188/256
├─ bloco 03 ─────────────────┤
│ [1, ...]                   │ 178/256  ← Nike migrada pelo UPDATE
└────────────────────────────┘

• ⚠️ Leitura adotada para brand: first-fit ao pé da letra (cada INSERT procura o primeiro bloco com espaço). Com "encher o último bloco", a Mizuno iria para um bloco 03 próprio, e a Nike cresceria no lugar (128 + 50 = 178 cabe em 243). Escreva na prova a regra que aplicou.
• ⚠️ Header de bloco não descontado, porque o enunciado não dá o tamanho dele.
• 📌 RV6, RV7 e AMP têm exatamente 46 B: o exercício foi montado para o AMP cair no buraco do RV6.

⚠️ 9. Pegadinhas

• CHAR(n) ocupa $n$ caracteres sempre; VARCHAR ocupa só o que foi usado.
• Conte espaço e hífen. Confira os nomes letra a letra: um caractere a mais muda o bloco.
• PCTFREE vale para o INSERT. O UPDATE usa a reserva. Arredonde o limite para baixo.
• First-fit volta aos blocos do começo: uma tupla nova pode cair num bloco antigo.
• DELETE não compacta nem move ninguém; só cria buraco na free list.
• UPDATE que não cabe migra: o rid muda, e todos os índices da tabela são corrigidos. A FK de outra tabela não muda.
• O arquivo não encolhe: um bloco esvaziado continua contado no header.

🔁 10. Variações que podem cair